package com.example.myletcodelearing.sort

import kotlin.jvm.JvmStatic
import com.example.myletcodelearing.sort.QuickSort
import java.lang.StringBuilder

/**
 * @author tgw
 * @date 2022/10/9
 * @describe
 */
/**
 * 快速排序
 *
 * @author 起凤
 * @description: TODO
 * @date 2022/4/11
 */
object QuickSort {
    @JvmStatic
    fun main(args: Array<String>) {
        val arr = intArrayOf(1, 5, 6, 2, 3, 4)
        print(quickSort(arr))

//        int[] arr1 = {2, 3, 1, 4, -1, 8, -1};
//        print(quickSort(arr1));
//
//        int[] arr2 = {-1, 7, 1, 4, 5, 8, 7};
//        print(quickSort(arr2));
    }

    private fun quickSort(arr: IntArray?): IntArray? {
        if (null != arr && arr.size > 0) {
            quickSortCore(arr, 0, arr.size - 1)
        }
        return arr
    }

    private fun quickSortCore(arr: IntArray, p: Int, r: Int) {
        if (p >= r) {
            return
        }
        val q = partition(arr, p, r)
        quickSortCore(arr, p, q - 1)
        quickSortCore(arr, q + 1, r)
    }

    /**
     * [p,i] 小于 arr[r]的区域
     * [i+1,j-1] 大于 arr[r]的区域
     * [j,r-1]  未处理的区域
     * r 下标默认是分区点参照的元素
     * p,j,i,r 均指下标,arr[r]指参照数
     *
     * @param arr
     * @param p
     * @param r
     * @return
     */
    private fun partition(arr: IntArray, p: Int, r: Int): Int {
        // 初始时设置i= -1,表示小于参照数的区域是空,i标识小于参照数的区域末尾位置
        var i = p - 1
        // 扫描未处理区域和挨个和参照数进行比较
        for (j in p until r) {
            // 比参照数小的放到[p,i]区域,[p,i]区域就开始扩大了
            if (arr[j] < arr[r]) {
                swap(arr, i + 1, j)
                i++
            }
        }
        // 再把参照数放到比它小的区域的后一个下标位置,这样 参照数左侧就是全部小于参照数的数，右侧就是大于参照数的数，可以继续往下拆分左右2侧递归了
        swap(arr, i + 1, r)
        return i + 1
    }

    private fun swap(arr: IntArray, i: Int, j: Int) {
        val temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }

    private fun print(sort: IntArray?) {
        val builder = StringBuilder()
        for (i in sort!!.indices) {
            builder.append(sort[i]).append(",")
        }
        println(builder)
    }
}